-----------------------------------------------------------------------------------------------------------------------
-- fiboncci : resuelve dado un numero natural ingresado su serie de fibonacci correspondiente.
fibonacci = evalDP (\x->x<=1) (\x->1) (\x -> [x-1,x-2]) (\l -> (head l)+(last l))

--esSubSeq : Resuelve el problema de que dado un par de secuencias p y t, determina si p es subsecuencia (de elementos contiguos) de t.
-- para su resolucion se utilizo la nocion de programacion dinamica con memorizacion.
esSubSeq :: Eq a => ([a],[a]) -> Bool
esSubSeq  = evalDP (isBase) (base) (split) (join) 

----------------------------------------------------------------------------------------------------------------------
--  isBase : distingue  las entradas, separando los casos base de los casos complejos.
-- En nuestro caso la longitud del texto ingresado debe ser igual o menor que la longitud del patron. 
-- ejemplo 0 : sea ("diseño","diseño") la tupla ingresada en este case ingresara al base dado a que sus longitudes son iguales.
-- ejemplo 1 : sea ("di","diseño") la tupla ingresada en este caso ingresara al base dado a que la long del texto es menor que la long del patron.
--ejemplo 3 : sea ("diseño","di") la tupla ingresada en este caso no ingresara al base dado a que la long del texto es mayor que la long del patron. 
isBase ::Eq a => ([a],[a]) -> Bool 
isBase x = length(fst(x)) ==length(snd(x)) || length(fst(x)) < length(snd(x))
----------------------------------------------------------------------------------------------------------------------
-- base : es el proceso directo luego de la evaluacion del isBase retorna true o false de acuardo a : 
-- ejemplo 0 :  "diseño" = "diseño" => True , dado a que las listas son iguales. 
-- ejemplo 1 :  "di" ="diseño"  => False ,  dado a que el texto diferente del patron.
--ejemplo 3 :  "" ="diseño"  => False ,  dado a que el texto diferente del patron.
--ejemplo 4 :  "" = ""  => True ,  dado a que el texto es igual al patron.

base :: Eq a => ([a],[a]) -> Bool
base x = (fst x)==(snd x)
---------------------------------------------------------------------------------------------------------------------
-- Split : dada una entrada compleja (no base), descompone a la misma en un numero de entradas mas simples.
-- ejemplo 0 : sea  ("diseño" ,"se")  la tupla que no ingreso por isBase, entonces nuestro split descompondra esta tupla en una lista de tuplas [t1,t2]
--donde la t1 sera ("iseño","se") y t2 sera ("diseñ","se") ,  entonces la t1 es el texto sin la primer letra y el t2 sera el texto sin la ultima letra ,
-- el patron en ambos casos no se modifica.
split :: Eq a => ([a],[a]) -> [([a],[a])] 
split x = [(tail (fst x),snd x),(init (fst x),snd x)] 
---------------------------------------------------------------------------------------------------------------------
-- join : dadas las soluciones a las entradas mas simples creadas por split, construye una solucion al problema original.
-- ejemplo 0 : dada la solucion simple creada por el split ("di","se") esta ingresara por el caso base generando un bool , por otro lado en la misma rama en el 
-- split se genero otra tupla ("se","se")  esta tambien ingresara por el caso base y  generara otro bool , el join tomara esta lista de estados y retornara 
-- un  veredicto, en este ejemplo true, el patron fue encontrado en el texto.
 
join :: [Bool] -> Bool
join xs = (head xs) || (last xs)


-- ########################################################################################################################
{-- Dados isBase base split join , se puede construir un algoritmo basada en memorizacion para resolver el problema. En Haskell, se puede
sintetizar este proceso mediante una funcion de alto orden, que tome por entradas todos los elementos anteriores que
caracterizan una solucion por programacion Dinamica, y los combine para conseguir implementar la funcion correspondiente: --}
evalDP :: Eq a => (a-> Bool) -> (a -> b) -> (a -> [a]) -> ([b] -> b) -> a -> b
evalDP isBase base split join x = solution x (evalDPStore isBase base split join x [])

-- ########################################################################################################################
{-- evalDPStore, que es la encargada de hacer la evaluacion y manejar la cache (representada por una lista, inicialmente vacia --}
evalDPStore :: Eq a => (a -> Bool) -> (a -> b) -> (a -> [a]) -> ([b] -> b) -> a -> [(a,b)] -> [(a,b)]
evalDPStore isBase base split join x cache | solved x cache = cache
                                           | isBase x = (x,(base x)) : cache 
                                           | otherwise = (x,calSol) : recursion 
                                     where  
                                        calSol = join (map (\e -> (solution e recursion) ) (split x))				       
					recursion = foldr (evalDPStore isBase base split join) (cache) (split x) 	

-- #########################################################################################################################
-- solution : dado un que el elemento fue resuelto devuelve el resultado del mismo.
solution :: Eq a => a -> [(a,b)] -> b
solution y (xs)  = snd (head ([ n| n <- xs , fst (n) == y ]))
---------------------------------------------------------------------------------------------------------------------------
--solved:  devuelve si el elemento fue resuelto o no.
solved :: Eq a => a -> [(a,b)] -> Bool
solved x ys = length [n| n<- ys , x == fst(n)] == 1
-- ########################################################################################################################


